In the field of systems design, considerable attention has been devoted to the analysis and synthesis of so-called concurrent systems--that is, systems in which various events may occur in an arbitrary order relative to one another, such order not being known or ascertainable at the time the system (or one's analysis of the system) is started. Concurrent systems are important in, among other areas, logic design and computer architecture. In those areas, concurrent systems are viewed as useful for providing more processing power and speed than can a conventional single processor or sequential logic system.
For nearly half a century, general purpose digital computers have been based on the so-called Von Neumann model of a central processing unit connected to a random-access memory in which a program may be stored. The operation of such machines is inherently sequential; that is, the processor performs only one operation at a time, in an order defined by the program. In recent years, there has been a concerted effort to develop computers capable of ever greater performance (defined as the ability to perform more computations of a given type in a unit of time--the measure typically used is the number of millions of instructions per second, MIPS, or the number of floating point operations per second, FLOPS, which the computer can execute). System speed has been improved by increasing the operating speed of individual processors, and by the development and use of multi-processor architectures (particularly architectures employing multiple microprocessors) and so-called distributed and parallel processing arrangements. One interesting multi-processor system is the so-called "Configurable, Highly Parallel," or "CHiP", computer and its "Poker" parallel programming environment, which was developed at Purdue University, as described in L. Snyder, "Parallel Programming and the Poker Programming Environment," IEEE Computer, July 1984, at 27. The CHiP computer comprises a rectangular array of microprocessors in which each microprocessor is connectable to its neighbors through simple switches.
Such advances in architecture, however, are not without their disadvantages. When multiple processors are employed, a considerable amount of overhead is added, simply to coordinate the activities of the various computing elements. Moreover, each processor is typically still a Von Neumann machine, so it can only execute one operation at a time. Thus concurrency can only be achieved at that granularity or higher. Increasing the number of processors operating in parallel, to increase concurrency, unfortunately requires a disproportionate increase in the housekeeping tasks required for coordination of their activities.
Further, the concept of doing one thing at a time usually pervades the design of each single processor. That is, a given operation may only require the use of a small portion of a processor's logic; the remainder of its logic circuits may remain idle and unproductive while the operation is being performed. This is largely a result of using a microprocessor, or the like, as the kernel of processing power.
When speed of operation is a factor, however, microprocessors may not provide an adequate solution to a problem; even relatively simple tasks may require so many instruction cycles to accomplish that the effective speed of the microprocessor may not be sufficient.
Against this background, it has been observed that many complex and demanding problems can be formulated for execution with large degrees of concurrency--in the thousands, or even millions, of loosely coupled processes.
The development of concurrent or parallel processing environments has not relied solely on multi-microprocessor architectures. Some non-Von Neumann architectures have been proposed or built. However, they have either been confined to special purpose environments or they have failed to provide sufficient performance advantages to justify their cost.
Of course, there have also been developments in the areas of logic circuit design, including the design of general purpose logic arrays, including arrangements such as programmable logic arrays (PLA's). However, various problems have been identified with programmable logic devices, among which are the following: (1) lack of silicon efficiency--due to the fact that programming such devices by blowing fuses inherently wastes large numbers of gates; (2) lack of nondestructive testing techniques in those situations where gates can only be checked by blowing fuses; (3) lack of reprogrammability of many such devices, such as those in which fuses are blown; (4) structure which is too rigid, causing the user to encounter difficulties in implementing circuits; (5) lack of sufficient exclusive-OR gates for the implementation of complex arithmetic logic; and (6) undesirable tradeoffs between speed, power and function. The latter complaint reflects the fact that many programmable logic devices have been implemented with bipolar technology. Recently, some of these problems have been reduced in magnitude by the use of CMOS fabrication technology and the advent of erasable programmable logic which uses EPROM cells instead of fuses, to program the device.
There is thus widespread recognition of the desirability and promise of an uncommited array of logic devices which can be transformed into an application-specific integrated circuit. Prior attempts to provide such devices, however, have encountered problems such as those discussed above, as well as problems providing sufficiently general functionality. Additionally, the user must have a detailed technical knowledge of the underlying circuitry and of how to make use of that circuitry.
One of the more interesting attempts to achieve a general purpose structure is shown in U.S. Pat. No. 4,068,214, issued Jan. 10, 1078 to Suhas S. Patil. That patent discloses an asynchronous logic array usable in implementing a large class of Petri Nets. Digressing briefly, a Petri Net is a formal model for concurrent systems. Petri Nets may be used to model a wide range of systems, and can represent arbitrarily complex behavior. The mathematical definition of a Petri Net is well-known and can be found in any of a number of references. One good discussion is contained in T. Agerwala, "Putting Petri Nets to Work," IEEE Computer, December 1979, at 85-94, which is hereby incorporated by reference for its discussion of Petri Nets. For the purpose of establishing the lexicon, however, it is appropriate to note that a Petri Net is a bipartite, directed graph N=(T, P, A), where T denotes a set of "transitions" (or "events"), P is a set of "places" (or "states") and A is a set of directed arcs from transitions to places and vice versa. The union of transitions and places defines the "nodes" of the system. "Tokens" may be assigned to places in the net. A transition is said to be "enabled" in a Petri Net if each of its input places has a token. An enabled transition can "fire" by removing a token from each of its input places and putting a token in each of its output places. Tokens are indivisible; that is, a token can be removed from a place by only one transition. In general, the firing of transitions proceeds asynchronously.
It merits comment that Petri Nets can represent both concurrency and conflict, for much of their power flows from this property. "Concurrency" means that transitions are relatively independent; that is, the firing of a pair of transitions can occur in an arbitrary order if both transitions are enabled and the transitions do not share input places. "Conflict" occurs when two transitions that share an input place are enabled at the same time, such that the firing of one of those transitions disables the other.
The transitions, places and tokens of a Petri Net are readily mapped to the variables occurring in physical systems. For example, a net could represent a manufacturing plant, with input places representing materials reaching work stations, transitions representing processing taking place at the work station, output places representing the results of the work station's operation and tokens representing the quanta of material required to reach a work station before it can perform its processing. Digital systems (both synchronous and asychronous) are also readily representable using Petri Nets.
The use of Petri Nets for system modelling makes available a variety of techniques for system synthesis and analysis.
The implementation of Petri nets in computer circuitry (i.e., digital logic) has been studied by others, and various types of circuitry have been proposed for such implementations. Frequently, the goal has been to provide a general-purpose implementation of Petri Nets, capable of embodying all or nearly all types of Petri Nets. According to one approach, circuit modules are substituted directly for transitions and places. However, due to the need to account for all types of Petri Nets, this generally has led to circuit realizations that are fairly complex. Another approach has been to provide a basic collection of Petri Net functions and corresponding speed-independent hardware blocks. Complete circuits are assembled directly from these blocks. A transistor-level implementation has also been described in the literature for various circuits which can be combined to create realizations for Petri Nets of different types. See E. Pacas-Skewes, "A Design Methodology for Digital Systems Using Petri Nets," PhD diss., Univ. of Texas at Austin, 1979. The Pacas-Skewes approach, however, does not involve reprogrammable logic or the use of regular arrays of devices. Still another implementation is shown in U.S. Pat. No. 4,068,214 to Patil. There, Patil describes an asynchronous logic array, but that array implements control structures, not data structures. The array is said to consist of columns and rows. The rows act as transitions and alter the states of the columns, which act as places. Normally rows operate independently of each other, but sometimes a device called an arbiter is employed to ensure that rows connected to it fire one at a time, in accordance with some priority scheme.
Another structure has been described in S. S. Patil and T. A. Welch, "A Programmable Logic Approach for VLSI," IEEE Transactions on Computers, Vol. C-28, No. 9, September 1979, at 594-601. The Patil and Welch structure is a form of programmable logic array which provides conventional AND and OR functions, while also containing flip-flops distributed throughout the array. It allows portions of the array to be used for independent tasks and can be operated in synchronous or asynchronous modes. However, there are restrictions on the segmentation of areas of the array inasmuch as control is row and column oriented. Columns may be divided into independent column segments at points provided, typically, every eight rows; while rows may be divided into independent row segments at breakpoints provided, typically, every four columns. Every column segment must contain at least one flip-flop. Each logical column can either act as a stored binary variable, or it can perform the logical OR function of the row inputs. When the column segment represents a stored variable, the values can be set and reset by the rows. Each row is an implicant or conjunction term over the selected column variables; a column input may be either the column value, its complement or there may be no connection from the column to that row. These variables are ANDed to form the row value. Though this structure is interesting, it is not designed to implement Petri Nets directly. Further, it is unclear that this approach is adaptable to a practical design environment for constructing complex systems.
It is, therefore, an object of the present invention to provide a computational apparatus and architecture in which concurrency can be extended to a much lower level than has generally been heretofore achieved.
It is a further object of the invention to provide a computational apparatus and method which provides a greater degree of concurrency than has previously been achieved.
Still another object of the invention is a universal digital logic circuit which can be employed to implement a large class of logic operations.
Yet another object of the invention is to provide a reprogrammable digital logic device which can be programmed and reprogrammed easily to implement a large class of logic operations.
Another object of the invention is to provide a reprogrammable digital logic device which can be programmed and reprogrammed easily to realize a large class of Petri Nets.
Still another object is to provide a reprogrammable digital logic cell which can be connected to other such cells to form an array of cells in a regular pattern in at least two dimensions.
A further object of the invention is to provide such an array wherein the cells operate asynchronously, for implementation of speed-independent logic.
Another object of the invention is to provide a method and an environment to facilitate the programming of the reprogrammable logic device and systems employing the reprogrammable logic device.
A still further object of the invention is to provide reprogrammable logic and a user-friendly programming environment therefor, to reduce the time required for the development of a large class of digital systems.
Yet another object of the invention is to allow a manufacturer or system developer to work with a reduced parts inventory for digital logic, by providing a reprogrammable logic element which is usable for implementing a large class of digital functions.